package com.atwy.algorithm;

/**
 * @Author: 小王子火
 * @Date: 2022/3/12
 * 分治算法：分-解-合
 * 1、分解：将原问题分解成若干个规模较小，相互独立，与原问题形式相同的子问题
 * 2、解决：若子问题鬼灭较小而容易被解决则直接解决，否则递归地解各个子问题
 * 3、合并：将各个子问题的解合并为原问题的解
 */
public class DivideAndConquer {

    public static void main(String[] args) {
        testHanoiTower();
    }

    /**
     * 汉诺塔问题：
     * 有三根柱子，在一根柱子上从下往上安装大小顺序摞着64片黄金圆盘，
     * 要求把圆盘从下面开始按大小顺序重新摆放在另一根柱子上，
     * 并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘
     * <p>
     * 思路：
     * 假设柱子编号A、B、C
     * 1、我们先考虑只有一个盘的情况，A->C
     * 2、如果有两个盘，则需要按照
     *      1）先把最上的盘 A->B
     *      2) 把最下面的盘 A->C
     *      3) 把B塔的所有盘B->C
     *
     * 3、三个盘，可以把最上面两个看成一个盘，那这个问题就变成两个盘的问题了
     * ...
     * 如果有n个盘，可以看成两部分，上面n-1是一个部分，最下面第n个盘是一个部分，
     * 这样又变成了两个盘的问题
     */
    public static void testHanoiTower() {
        System.out.println("这是汉诺塔问题--开始");
        // 柱子名
        char a = 'A';
        char b = 'B';
        char c = 'C';
        // 盘子的个数
        int n = 3;
        hanoiTower(n, a, b, c);

        System.out.println("这是汉诺塔问题--结束");
    }

    /**
     * 汉诺塔问题递归主体
     *  目的是：把A塔的盘子移动到C塔，这里要借助B塔进行移动
     * @param n
     * @param a
     * @param b
     * @param c
     */
    private static void hanoiTower(int n, char a, char b, char c) {
        if (n == 1) {
            // 只有一个的时候只需要从A移动到C就可以了
            System.out.println("第1个盘从" + a + "->" + c );
        }else{
            // 2个及以上时
            //先把最上的盘 A->B，这里可能会借助C塔
            hanoiTower(n-1,a,c,b);
            //把最下面的盘 A->C
            System.out.println("第" + n + "个盘从" + a + "->" + c );
            //把B塔的所有盘B->C
            hanoiTower(n-1,b,a,c);
        }
    }
}
